package com.laotang.第_11_章_数学.力扣_149_直线上最多的点数;

import java.util.HashMap;
import java.util.Map;

public class _149_max_points_on_a_line {

    public int maxPoints(int[][] points) {
        if (points == null) return 0;
        if (points.length <= 2) return points.length;

        int res = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            map.clear();
            int currMax = 0;
            for (int j = i + 1; j < points.length; j++) {
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                int gcd = gcd(x, y);
                if (gcd != 0) {
                    x /= gcd;
                    y /= gcd;
                }
                // (y, x) 二元组作为 key
                String slope = y + "-" + x;
                int cnt = map.getOrDefault(slope, 0) + 1;
                currMax = Math.max(currMax, cnt);
                map.put(slope, cnt);
            }
            res = Math.max(res, currMax + 1);
        }
        return res;
    }

    // 求分子和分母的最大公约数
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}
